class Solution:
  def spiralOrder(self, matrix: list) -> list:
    if not matrix: return []
    rows, cols = len(matrix), len(matrix[0])
    row, col = 0, 0
    visited = [[False for j in range(cols)] for i in range(rows)]
    visited_count = 0
    res = []
    # 方向控制，R、D、L、U代表右、下、左、上
    direction = 'R'
    while True:
      if visited_count >= rows * cols: break
      res.append(matrix[row][col])
      visited[row][col] = True
      visited_count = visited_count + 1
      if direction == 'R':
        if col + 1 < cols and not visited[row][col + 1]:
          col = col + 1
        else:
          row = row + 1
          direction = 'D'
      elif direction == 'D':
        if row + 1 < rows and not visited[row + 1][col]:
          row = row + 1
        else:
          col = col - 1
          direction = 'L'
      elif direction == 'L':
        if col - 1 >= 0 and not visited[row][col - 1]:
          col = col - 1
        else:
          row = row - 1
          direction = 'U'
      else:
        if row - 1 >= 0 and not visited[row - 1][col]:
          row = row - 1
        else:
          col = col + 1
          direction = 'R'
    return res


'''
STATUS: SOLVED
TRIES:  1
TIME:   64 MS
MEMORY: 13.8 MB
'''
if __name__ == "__main__":
  solution = Solution()
  # data = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
  # data = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]
  data = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
  print(solution.spiralOrder(data))
